package gold.gold01;

/**
 * 中等
 */
public class S0204分割链表 {
    // 100, 59 把每个比x小的都移到表头
    // 对于java来说, 内存消耗并没有意义, 大头都是jvm, 运行不同次数获得的排名大相径庭。
    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null) return head;

        ListNode node1 = head;
        ListNode node2 = head.next;
        while(node2 != null){
            if(node2.val < x){
                // 移到链表头
                node1.next = node2.next;
                node2.next = head;
                head = node2;
                node2 = node1.next;
            }else{
                node1 = node1.next;
                node2 = node2.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(6);
        head.next = new ListNode(4);
        head.next.next = new ListNode(31);
        head.next.next.next = new ListNode(8);
        head.next.next.next.next = new ListNode(2);
        ListNode result = new S0204分割链表().partition(head, 5);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
}
